package com.wenhai.liuyubobobo.imooc.search;


/**
 * 第一版并查集实现
 *
 * @author wenhai
 * @date   2021/3/29
 */
public class UnionFind1 implements UnionFind {
    private final int[] ids;


    public UnionFind1(int size) {
        ids = new int[size];
        for (int i = 0; i < ids.length; i++) {
            ids[i] = i;
        }
    }


    @Override
    public int size(){
     return ids.length;
    }

    @Override
    public void union(int q, int p){
        int qId = find(q);
        int pId = find(p);
        if (qId == pId) {
            return;
        }
        for (int i = 0; i < ids.length; i++) {
            if (ids[i] == qId) {
                ids[i] = pId;
            }
        }
    }

    @Override
    public boolean isConnected(int q, int p){
        return find(q) == find(p);
    }

    private int find(int index) {
        if (index < 0 || index >= ids.length) {
            throw new IndexOutOfBoundsException(String.valueOf(index));
        }
        return ids[index];
    }


}
